(1) Field of the Invention
The present invention relates to the field of searching entries within an allocation vector to discover vacant locations of a resource buffer. Specifically, the present invention relates to the field of searching an entry vector, or portions thereof, using various search approaches for a predetermined number of vacant entries within a reservation station buffer.
(2) Prior Art
Modem microprocessors are gaining the ability to execute portions of several instructions in parallel during a single clock cycle. These microprocessors are called superscalar microprocessors and have pipelined and/or superscalar architecture. In effect, different stages of execution can be perforated by a microprocessor during a single clock cycle for several different microprocessor instructions. For this reason and others, microprocessors having this ability must be able to keep track of and store information regarding several instructions at the same time and communicate this information to and from several different portions of the microprocessor in a parallel fashion. Also, because of the high operating frequencies of modem pipelined microprocessors, this instruction information must be transmitted very quickly, usually during a single clock cycle of an oscillator operating at 150-200 Megahertz. Therefore, it becomes advantageous to be able to communicate instructions and instruction data very quickly in a parallel fashion to the various units of a microprocessor.
One component within a microprocessor that must receive information regarding instructions that are to be executed by a microprocessor is the instruction scheduler. The instruction scheduler holds information regarding the current instructions that are being executed as well as any data or information that is used by or in conjunction with the current instructions. The instruction scheduler has a finite memory storage capacity. Therefore, new and recent instruction information that is to be placed into the scheduler by the microprocessor must first obtain enough memory location vacancies within the instruction scheduler. That is to say, there must first be room within the scheduler before instruction information can be placed into the instruction scheduler.
A specialized deallocation vector is used by the instruction scheduler in order to indicate to the microprocessor which entries in the instruction scheduler are free and which are taken. In prior art implementations, the microprocessor would scan, one by one, each entry in the deallocation vector to locate one particular free entry of the instruction scheduler in order to store recent instruction data. However, with the introduction of microprocessors having superscalar architecture, the microprocessor must be able to search, at the same instant, the deallocation vector for up to several free entries to store information regarding several instructions during the same clock cycle. Further, as the time period between clock cycles shortens as microprocessors become faster and faster, it is important that the deallocation vector be searched very quickly as to not delay the processing of the microprocessor. Also, prior art schemes processed buffer entries that become vacant in order. What is needed is a mechanism for locating entries from a buffer wherein instruction information becomes vacant out of order. The present invention provides such functionality.
Prior art implementations used to search a deallocation vector in order to find vacancies within the instruction scheduler do not operate fast enough to complete processing within only one clock cycle (which may be on the order of 1/150.sup.th of a microsecond) or within one half clock cycle (which may be 1/300.sup.th of a microsecond) of modern superscalar microprocessors. It is not practical, given the environment of a pipelined microprocessor, to sequentially search each and every entry in a deallocation vector in order to discover, at the same instant, several vacant entries within the instruction scheduler. Since it is desired for pipelined microprocessors to execute portions of several instructions in parallel, it is unacceptable for there to be any delays associated with the search procedure of the deallocation vector of the instruction scheduler. This procedure must operate within a single clock cycle. Delays associated with such a task would reduce overall microprocessor efficiency and speed. Further, such processing delays may tend to eliminate the expansive advantages offered by microprocessors adopting pipeline architecture and associated microprocessor technology.
Therefore, what is desired is a processing scheme and apparatus that would allow very rapid searching of a deallocation vector in order to find, in one clock cycle, several vacant entries within an instruction scheduler. The present invention offers such advantageous capability.
Accordingly, it is an object of the present invention to provide a method and apparatus for searching a deallocation vector, within a single clock cycle, in order to locate several vacancies within a reservation station of an instruction scheduler. It is another object of the present invention to provide the above capability so that a pipelined architecture microprocessor can store instruction information for several instructions, which are or will be currently executed, into the instruction scheduler within the period one clock cycle. It is further an object of the present invention to provide such a system that operates very rapidly and will complete within one half of a clock cycle of the microprocessor, which may be less than 1/300.sup.th of a microsecond.
It is an additional object of the present invention to provide the above using various alternate searching techniques. Other objects of the present invention not specifically mentioned herein will become clear within the remainder of the discussions below.